package sword_to_1;

public class LeeCode_14_2 {
    public static void main(String[] args) {
        System.out.println(cuttingRope(1000));
    }
    private static int cuttingRope(int n2) {
        long n = n2;
        if (n == 3)
            return 2;
        if (n == 2)
            return 1;
        long ans = 1;
        long c = n / 3;
        long yu = n % 3;
        if (yu == 1){
            for (int i = 0; i < c - 1; i++) {
                ans *= 3;
                if (ans > 1000000007){
                    ans %= 1000000007;
                }
            }
            ans *= 4;
            if (ans > 1000000007){
                ans %= 1000000007;
            }
        }else {
            for (int i = 0; i < c; i++) {
                ans *= 3;
                if (ans > 1000000007){
                    ans %= 1000000007;
                }
            }
            ans *= yu == 0 ? 1 : yu;
            if (ans > 1000000007){
                ans %= 1000000007;
            }
        }
        return (int) ans;
    }
}
